Traditional systems include a processor, a L1 cache, a L2 cache, and memory. The L1 cache is a form of fast memory (holding recently accessed data), designed to speed up subsequent access to the same data. The L1 cache, specifically, is located on or close to the microchip containing the processor. The L2 cache is similar to the L1 cache except that it contains data that was not as recently accessed as the data in the L1 cache. Additionally, the L2 cache typically has a larger memory capacity and a slower access time.
The memory is typically random access memory (RAM). When a load request is generated on the system, a virtual address is sent from the processor to a corresponding TLB (not shown). The TLB converts the virtual address into a physical address that is subsequently sent to the L1 cache. In one embodiment of the invention, associated with the L1 cache is an L1 cache tag array. The L1 cache tag array is an index of data stored in the L1 cache. If the physical address, sent from the TLB to the L1 cache, is present in the L1 cache tag array, then the datum corresponding to the physical address is retrieved and sent to the processor. If the physical address is not present in the L1 cache tag array, then the L1 cache forwards the physical address to the L2 cache.
If the physical address is found in the L2 cache tag array, then a cache line associated with the physical address is retrieved from the L2 cache and sent to the L1 cache. One skilled in the art will appreciate that the cache line is the unit of transfer between the L2 cache and the L1 cache. Once the L1 cache receives the cache line, the L1 cache retrieves and forwards the requested datum within the cache line to the processor.
If the physical address is not found in the L2 cache tag array, then the L2 cache forwards the physical address to memory. Once the physical address is found in memory, the entire cache line on which the requested datum is located is retrieved and sent to the L2 cache. The L2 cache subsequently forwards the entire cache line to the appropriate L1 cache. Upon receipt of the entire cache line, the L1 cache forwards the requested datum within the cache line to the appropriate processor.
Each of the aforementioned caches (i.e., L1 cache and L2 cache) has a fixed size. Accordingly, a cache may become full (i.e., no more data may be stored in the cache). When a cache becomes full, one or more cache lines must be evicted, prior to loading additional data into the cache.